Semi%2DSupervised Dimension Reduction for Multi%2DLabel Classification.

Flexible constrained spectral clustering.

Unifying dependent clustering and disparate clustering for non%2Dhomogeneous data.
Modern data mining settings involve a combination of attributevalued descriptors over entities as well as specified relationships between these entities. We present an approach to cluster such non-homogeneous datasets by using the relationships to impose either dependent clustering or disparate clustering constraints. Unlike prior work that views constraints as boolean criteria, we present a formulation that allows constraints to be satisfied or violated in a smooth manner. This enables us to achieve dependent clustering and disparate clustering using the same optimization framework by merely maximizing versus minimizing the objective function. We present results on both synthetic data as well as several real-world datasets.
A SAT%2Dbased Framework for Efficient Constrained Clustering.

Discovering Contexts and Contextual Outliers Using Random Walks in Graphs.

A principled and flexible framework for finding alternative clusterings.

Knowledge Driven Dimension Reduction for Clustering.
As A.I. algorithms are applied to more complex domains that involve high dimensional data sets there is a need to more saliently represent the data. However, most dimension reduction approaches are driven by objective functions that may not or only partially suit the end users requirements. In this work, we show how to incorporate general-purpose domain expertise encoded as a graph into dimension reduction in way that lends itself to an elegant generalized eigenvalue problem. We call our approach Graph-Driven Constrained Dimension Reduction via Linear Projection (GCDR-LP) and show that it has several desirable properties. 1
A principled and flexible framework for finding alternative clusterings.


Clustering with Constraints.
This paper studies the problem of building clusters of music tracks in a collection of popular music in the presence of constraints. The constraints come naturally in the context of music applications. For example, constraints can be generated from the background knowledge (e.g., two artists share similar styles) and the user access patterns (e.g., two pieces of music share similar access patterns across multiple users). We present an approach based on the generalized constraint clustering algorithm by incorporating the constraints for grouping music by “similar ” artists. The approach is evaluated on a data set consisting of 53 albums covering 41 popular artists. The “correctness ” of the clusters generated is tested using artist similarity provided by All Music Guide. 1

Data preparation using data quality matrices for classification mining.

Finding Alternative Clusterings Using Constraints.

Intractability and clustering with constraints.

Efficient incremental constrained clustering.
Clustering with constraints is an emerging area of data mining research. However, most work assumes that the constraints are given as one large batch. In this paper we explore the situation where the constraints are incrementally given. In this way the user after seeing a clustering can provide positive and negative feedback via constraints to critique a clustering solution. We consider the problem of efficiently updating a clustering to satisfy the new and old constraints rather than re-clustering the entire data set. We show that the problem of incremental clustering under constraints is NP-hard in general, but identify several sufficient conditions which lead to efficiently solvable versions. These translate into a set of rules on the types of constraints that can be added and constraint set properties that must be maintained. We demonstrate that this approach is more efficient than re-clustering the entire data set and has several other advantages.
Constraint%2Ddriven clustering.
Clustering methods can be either data-driven or need-driven. Data-driven methods intend to discover the true structure of the underlying data while need-driven methods aims at organizing the true structure to meet certain application requirements. Thus, need-driven (e.g. constrained) clustering is able to find more useful and actionable clusters in applications such as energy aware sensor networks, privacy preservation, and market segmentation. However, the existing methods of constrained clustering require users to provide the number of clusters, which is often unknown in advance, but has a crucial impact on the clustering result. In this paper, we argue that a more natural way to generate actionable clusters is to let the application-specific constraints decide the number of clusters. For this purpose, we introduce a novel cluster model, Constraint-Driven Clustering (CDC), which finds an a priori unspecified number of compact clusters that satisfy all user-provided constraints. Two general types of constraints are considered, i.e. minimum significance constraints and minimum variance constraints, as well as combinations of these two types. We prove the NP-hardness of the CDC problem with different constraints. We propose a novel dynamic data structure, the CD-Tree, which organizes data points in leaf nodes such that each leaf node approximately satisfies the CDC constraints and minimizes the objective function. Based on CD-Trees, we develop an efficient algorithm to solve the new clustering problem. Our experimental evaluation on synthetic and real datasets demonstrates the quality of the generated clusters and the scalability of the algorithm.
On Sample Selection Bias and Its Efficient Correction via Model Averaging and Unlabeled Examples.

The complexity of non%2Dhierarchical clustering with instance and cluster level constraints.

Editorial Special issue on mining low%2Dquality data.

Identifying and Generating Easy Sets of Constraints for Clustering.

When Is Constrained Clustering Beneficial%2C and Why%3F.
Several researchers have illustrated that constraints can improve the results of a variety of clustering algorithms. However, there can be a large variation in this improvement, even for a fixed number of constraints for a given data set. We present the first attempt to provide insight into this phenomenon by characterizing two constraint set properties: inconsistency and incoherence. We show that these measures are strongly anti-correlated with clustering algorithm performance. Since they can be computed prior to clustering, these measures can aid in deciding which constraints to use in practice.
Forecasting Skewed Biased Stochastic Ozone Days Analyses and Solutions.

Reverse testing an efficient framework to select amongst classifiers under sample selection bias.
One of the most important assumptions made by many classification algorithms is that the training and test sets are drawn from the same distribution, i.e., the so-called “stationary distribution assumption” that the future and the past data sets are identical from a probabilistic standpoint. In many domains of real-world applications, such as marketing solicitation, fraud detection, drug testing, loan approval, sub-population surveys, school enrollment among others, this is rarely the case. This is because the only labeled sample available for training is biased in different ways due to a variety of practical reasons and limitations. In these circumstances, traditional methods to evaluate the expected generalization error of classification algorithms, such as structural risk minimization, ten-fold cross-validation, and leave-one-out validation, usually return poor estimates of which classification algorithm, when trained on biased dataset, will be the most accurate for future unbiased dataset, among a number of competing candidates. Sometimes, the estimated order of the learning algorithms ’ accuracy could be so poor that it is not even better than random guessing. Therefore, a method to determine the most accurate learner is needed for data mining under sample selection bias for many real-world applications. We present such an approach that can determine which learner will perform the best on an unbiased test set, given a possibly biased training set, in a fraction of the computational cost to use cross-validation based approaches.
Measuring Constraint%2DSet Utility for Partitional Clustering Algorithms.
Abstract. Clustering with constraints is an active area of machine learning and data mining research. Previous empirical work has convincingly shown that adding constraints to clustering improves the performance of a variety of algorithms. However, in most of these experiments, results are averaged over different randomly chosen constraint sets from a given set of labels, thereby masking interesting properties of individual sets. We demonstrate that constraint sets vary significantly in how useful they are for constrained clustering; some constraint sets can actually decrease algorithm performance. We create two quantitative measures, informativeness and coherence, that can be used to identify useful constraint sets. We show that these measures can also help explain differences in performance for four particular constrained clustering algorithms. 1
When Efficient Model Averaging Out%2DPerforms Boosting and Bagging.
Abstract. Bayesian model averaging also known as the Bayes optimal classifier (BOC) is an ensemble technique used extensively in the statistics literature. However, compared to other ensemble techniques such as bagging and boosting, BOC is less known and rarely used in data mining. This is partly due to model averaging being perceived as being inefficient and because bagging and boosting consistently outperforms a single model, which raises the question: “Do we even need BOC in datamining?”. We show that the answer to this question is “yes ” by illustrating that several recent efficient model averaging approaches can significantly outperform bagging and boosting in realistic difficult situations such as extensive class label noise, sample selection bias and many-class problems. To our knowledge the insights that model averaging can outperform bagging and boosting in these situations has not been published in the machine learning, mining or statistical communities. 1
Active Learning with Partially Labeled Data via Bias Reduction.

An Improved Categorization of Classifier%27s Sensitivity on Sample Selection Bias.
A recent paper categorizes classifier learning algorithms according to their sensitivity to a common type of sample selection bias where the chance of an example being selected into the training sample depends on its feature vector   but not (directly) on its class label y. A classifier learner is categorized as &#034;local&#034; if it is insensitive to this type of sample selection bias, otherwise, it is considered &#034;global&#034;. In that paper, the true model is not clearly distinguished from the model that the algorithm outputs. In their discussion of Bayesian classifiers, logistic regression and hard-margin support vector machines, the true model (or the model that generates the true class label for every example) is implicitly assumed to be contained in the model space of the learner, and the true class probabilities and model estimated class probabilities are assumed to asymptotically converge as the training data set size increases. However, in the discussion of naive Bayes, decision trees and soft-margin support vector machines, the model space is assumed not to contain the true model, and these three classification algorithms are instead argued to be &#034;global learners&#034;. Here we argue that most classifier learning algorithms including those just discussed may or may not be affected by sample selection bias; this will depend on the dataset as well as the heuristics or inductive bias implied by the classifier learning algorithm and their appropriateness to the particular dataset. We make use of our earlier experimental results and produce additional results to illustrate our claims.
A Dynamic Adaptive Sampling Algorithm %28DASA%29 for Real World Applications Finger Print Recognition and Face Recognition.

Agglomerative Hierarchical Clustering with Constraints Theoretical and Empirical Results.
Abstract. We explore the use of instance and cluster-level constraints with agglomerative hierarchical clustering. Though previous work has illustrated the benefits of using constraints for non-hierarchical clustering, their application to hierarchical clustering is not straight-forward for two primary reasons. First, some constraint combinations make the feasibility problem (Does there exist a single feasible solution?) NP-complete. Second, some constraint combinations when used with traditional agglomerative algorithms can cause the dendrogram to stop prematurely in a dead-end solution even though there exist other feasible solutions with a significantly smaller number of clusters. When constraints lead to efficiently solvable feasibility problems and standard agglomerative algorithms do not give rise to dead-end solutions, we empirically illustrate the benefits of using constraints to improve cluster purity and average distortion. Furthermore, we introduce the new γ constraint and use it in conjunction with the triangle inequality to considerably improve the efficiency of agglomerative clustering. 1
Clustering with Constraints Feasibility Issues and the k%2DMeans Algorithm.
Recent work has looked at extending the k-Means algorithm to incorporate background information in the form of instance level must-link and cannot-link constraints. We introduce two ways of specifying additional background information in the form of # and # constraints that operate on all instances but which can be interpreted as conjunctions or disjunctions of instance level constraints and hence are easy to implement. We present complexity results for the feasibility of clustering under each type of constraint individually and several types together. A key finding is that determining whether there is a feasible solution satisfying all constraints is, in general, NP-complete. Thus, an iterative algorithm such as k-Means should not try to find a feasible partitioning at each iteration. This motivates our derivation of a new version of the k-Means algorithm that minimizes the constrained vector quantization error  but at each iteration does not attempt to satisfy all constraints. Using standard UCI datasets, we find that using constraints improves accuracy as others have reported, but we also show that our algorithm reduces the number of iterations until convergence. Finally, we illustrate these benefits and our new constraint types on a complex real world object identification problem using the infra-red detector on an Aibo robot.
An Ensemble Technique for Stable Learners with Performance Bounds.
Ensemble techniques such as bagging and DECORATE exploit the  &#034;instability&#034; of learners, such as decision trees, to create a diverse  set of models. However their application to stable learners such as  nave Bayes, does not yield as much improvement and can  sometimes degrade performance a claim we empirically verify in  this paper. But stable learners are desirable for their superior  performance on some problems and algorithmic simplicity. We  show that many learners commonly referred to as stable have  Gaussian posterior distributions. Given such a well defined  posterior distribution we can use both parametric and nonparametric  bootstrapping to create a process that approximates  taking draws from their posterior. By summing the joint  distribution of the instance and the class we are approximating  posterior model averaging a.k.a. the optimal Bayes classifier  (OBC) which is known to minimize the Bayes error. We refer to  our approach as bootstrap model averaging. Since model averaging  removes the model uncertainty it works best when there is much  model uncertainty and does no harm when there is little, a claim we  empirically verify. Since the Gaussian distribution is  mathematically well understood we can bound the increase over  the OBC error using a Chebychev bound as a function of the  number of models built. We empirically illustrate our approach&#039;s  usefulness and verify our bound&#039;s correctness.
Bayesian Model Averaging Across Model Spaces via Compact Encoding.
Bayesian Model Averaging (BMA) is well known for improving predictive accuracy by averaging inferences over all models in the model space. However, Markov chain Monte Carlo (MCMC) sampling, as the standard implementation for BMA, encounters difficulties in even relatively simple model spaces. We introduce a minimum message length (MML) coupled MCMC methodology, which not only addresses these difficulties but has additional benefits. We illustrate the methodology with a mixture component model example (clustering) and show that our approach produces more interpretable results when compared to Green&#039;s popular reverse jump sampling across model sub-spaces technique. The MML principle mathematically embodies Occam&#039;s razor by assigning penalized prior probabilities to complicated models. We find that BMA prediction based on sampling across multiple sub-spaces of different complexity makes much improved predictions compared to the single best (shortest) model.
Using the Central Limit Theorem for Belief Network Learning.
Learning the parameters (conditional and marginal probabilities) from a data set is a common  method of building a belief network. Consider the situation where we have many complete (no missing  values), same-sized data sets randomly selected from the population. For each data set we learn the  network parameters using only that data set. In such a situation there will be no uncertainty (posterior  distribution) over the parameters in each graph, however, how will the parameters learnt differ from data  set to data set? In this paper we show the parameter estimates across the data sets converge to a Gaussian  distribution with a mean equal to the population (true) parameters. This result is obtained by a straightforward  application of the central limit theorem to belief networks. We empirically verify the central  tendency of the learnt parameters and show that the parameters&#039; variance can be accurately estimated by  Efron&#039;s bootstrap sampling approach. Learning multiple networks from bootstrap samples allows the  calculation of each parameter&#039;s expected value (as per standard belief networks) and also its second  moment, the variance. Having the expectation and variance of each parameter has many potential  applications. In this paper we discuss initial attempts to explore their use to obtain confidence intervals  over belief network inferences and the use of Chebychev&#039;s bound to determine if it is worth gathering  more data for learning.
An Information Theoretic Optimal Classifier for Semi%2Dsupervised Learning.

Locating secret messages in images.
Steganography involves hiding messages in innocuous media such as images, while steganalysis is the field of detecting these secret messages. The ultimate goal of steganalysis is two-fold: making a binary classification of a file as stego-bearing or innocent, and secondly, locating the hidden message with an aim to extracting, sterilizing or manipulating it. Almost all steganalysis approaches (known as attacks) focus on the first of these two issues. In this paper, we explore the difficult related problem: given that we know an image file contains steganography, locate which pixels contain the message. We treat the hidden message location problem as outlier detection using probability/energy measures of images motivated by the image restoration community. Pixels contributing the most to the energy calculations of an image are deemed outliers. Typically, of the top third of one percent of most energized pixels (outliers), we find that 87% are stego-bearing in color images and 61% in grayscale images. In all image types only 1% of all pixels are stego-bearing indicating our techniques provides a substantial lift over random guessing.
A general approach to incorporate data quality matrices into data mining algorithms.
1st author&#039;s affiliation 1st line of address 2nd line of address Telephone number, incl. country code 1st author&#039;s email address
Further Applications of a Particle Visualization Framework.

Searching for Hidden Messages Automatic Detection of Steganography.

Visualizing Clustering Results.
Non-hierarchical clustering has a long history in numerical taxonomy [13] and machine learning [1] with many applications in fields such as data mining [2], statistical analysis [3] and information retrieval [17]. Clustering involves finding a specific number of subgroups (k) within a set of s observations (data points/objects); each described by d
Minimum Message Length Clustering Using Gibbs Sampling.
The K-Means and EM algorithms are popular in  clustering and mixture modeling due to their  simplicity and ease of implementation. However,  they have several significant limitations. Both  converge to a local optimum of their respective  objective functions (ignoring the uncertainty in the  model space), require the apriori specification of  the number of classes/clusters, and are  inconsistent. In this work we overcome these  limitations by using the Minimum Message  Length (MML) principle and a variation to the KMeans  /EM observation assignment and parameter  calculation scheme. We maintain the simplicity of  these approaches while constructing a Bayesian  mixture modeling tool that samples/searches the  model space using a Markov Chain Monte Carlo  (MCMC) sampler known as a Gibbs sampler.
Using Background Contextual Knowledge for Document Representation.
We describe our approach to document representation that  captures contextual dependencies between terms in a corpus and makes use  of these dependencies to represent documents. We have tried our  representation scheme for automatic document categorisation on the  Reuters&#039; test set of documents. We achieve a precision recall break even  point of 84% which is comparable to the best known published results. Our  approach acts as a feature selection technique that is an alternative to  applying the techniques from machine learning and numerical taxonomy.
Testing conformance to OSI standards.

